import java.io.*;
import java.util.*;

public class Lab1
{
	public static void main(String[] args)
	{
		new Lab1(args);
	}

	public Lab1(String[] args)
	{
		PathAlg algo = new ExhaustiveAlgorithm();
		if(args.length != 1)
		{
			System.err.println("Usage `java main FILE`");
			return;
		}
		algo.buildGraph(args[0]);
		long t = Calendar.getInstance().getTimeInMillis();
		algo.runAlgorithm();
		t = Calendar.getInstance().getTimeInMillis() - t;

		System.out.print("Min. Expected Latencey: "
			+ algo.getExpectedLatency() + "\nPath: ");
		
		for(int i : algo.getPath())
		{
			System.out.print((i+1) + " ");
		}

		System.out.println("\nExecution time in ms: " + t);
		System.out.println();
	}

	public abstract class PathAlg {
		// Result
		protected float expectedLatency = -1;
		protected int[] path = null;

		// Graph
		protected float[] probabilities  = null;
		protected int[][] costs = null;

		public abstract void runAlgorithm();
		
		public void buildGraph(String inputFile)
		{
			// Parse file and set up graph
			BufferedReader in;

			try
			{
				in = new BufferedReader(new FileReader(inputFile));
			}
			catch(FileNotFoundException ex)
			{
				System.err.println("File \"" + inputFile + "\" not found.");
				return;
			}
			
			String line;
			try
			{
				int i = 0;
				int numNodes = 0;
				while((line = in.readLine()) != null)
				{
					// First line should contain our array lengths
					if(i == 0)
					{
						numNodes = Integer.parseInt(line);
						costs = new int[numNodes][numNodes];
						probabilities = new float[numNodes];

						path = new int[numNodes];
						// Always visit first node first
						this.path[0] = 0;
					}
					// The next numNodes lines should contain probabilities
					else if(i <= numNodes)
					{
						probabilities[i-1] = Float.parseFloat(line);
					}
					// And the rest should hold our cost matrix
					else
					{
						String[] nums = line.split(" ");
						for(int j=0; j<nums.length; ++j)
						{
							costs[i-1-numNodes][j] = Integer.parseInt(nums[j]);
						}
					}
					i = i + 1;
				}
			}
			catch(IOException ex)
			{
				System.err.println("Error when reading file.");
			}
		}

		public int[] getPath()
		{
			if(this.path == null)
			{
				throw new IllegalStateException("Algorithm has not been run");
			}

			return this.path;
		}

		protected float calculateExpectedLatency(int[] path)
		{
			float sum = 0;
			int pathCost = 0;
			int lastNode = 0;
			for(int v : path)
			{
				// Do not need to calculate first step 
				if(v == 0)
				{
					continue;
				}

				pathCost += costs[lastNode][v];
				sum += probabilities[v]*pathCost;

				lastNode = v;
			}

			return sum;
		}

		public float getExpectedLatency()
		{
			if(this.path == null)
			{
				throw new IllegalStateException("Algorithm has not been run");
			}

			if(this.expectedLatency == -1)
			{
				this.expectedLatency = calculateExpectedLatency(this.path);
			}

			return this.expectedLatency;
		}

	}

	public class ExhaustiveAlgorithm extends PathAlg {
		public void runAlgorithm() {
			HashMap<Integer, Boolean> visited = new HashMap<Integer, Boolean>();
			visited.put(0, true);
			AlgRet newPath = visitRest(visited, new int[] { 0 });
			this.expectedLatency = newPath.expectedLatency;
			this.path = newPath.path;
		}

		private AlgRet visitRest(HashMap<Integer, Boolean> visited, int[] prePath) {
			AlgRet ret = null;

			for(int i=0; i<costs.length; i++) {
				if(visited.get(i) == null) {
					// The new, resulting path, after arriving at this node
					int[] pathToHere = new int[prePath.length + 1];
					// Copy previous nodes
					System.arraycopy(prePath, 0, pathToHere, 0, prePath.length);
					// Add current node last
					pathToHere[pathToHere.length - 1] = i;

					// Only leaf nodes calculate path length
					if(pathToHere.length == path.length) {
						return new AlgRet(calculateExpectedLatency(pathToHere), pathToHere);
					}
					else {
						// Mark current node as visited
						visited.put(i, true);

						// Get the shortest path from this node
						AlgRet newPath = visitRest(visited, pathToHere);

						// If this is the shortest, or the first, update return value
						if(ret == null || newPath.expectedLatency < ret.expectedLatency)
							ret = newPath;

						// We're leaving the node
						visited.remove(i);
					}
					
				}
			}
			return ret;
		}

		private class AlgRet {
			public float expectedLatency; 
			public int[] path;
			public AlgRet(float el, int[] p) { expectedLatency = el; path = p; }
		}
	}
}
